package linkedlist;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * 请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。
 * AllOne() 初始化数据结构的对象。
 * inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ，那么插入计数为 1 的 key 。
 *
 * dec(String key) 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ，
 * 那么需要将这个 key 从数据结构中删除。测试用例保证：在减少计数前，key 存在于数据结构中。
 *
 * getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 "" 。
 *
 * getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 "" 。
 */
class AllOne {
    public static void main(String[] args) {
        AllOne allOne = new AllOne();
        allOne.inc("a");
        allOne.inc("b");
        allOne.inc("c");
        allOne.inc("d");
        allOne.inc("a");
        allOne.inc("b");
        allOne.inc("c");
        allOne.inc("d");
        allOne.inc("e");
        allOne.inc("e");
        allOne.inc("c");
        allOne.inc("d");
        allOne.inc("d");
        allOne.inc("a");
        System.out.println(allOne.getMinKey());
    }
    Map<String,Integer> list;
    Map<Integer,String> counts;
    public AllOne() {
        list = new HashMap<>();
    }
    public void inc(String key) {
        int count;
        if (!list.containsKey(key)){
            count = 1;
        }else {
            count = list.get(key)+1;
        }
        list.put(key,count);
    }
    public void dec(String key) {
        int count = list.get(key);
        if(count == 1){
            list.remove(key);
            counts.remove(count);
        }else {
            list.put(key, list.get(key) - 1);
            counts.put(list.get(key) - 1,key);
        }
    }
    public String getMaxKey() {
        if(list.isEmpty()){
            return "";
        }
        int maxCount = 0;
        String result = "";
        Iterator<Map.Entry<String, Integer>> iterator = list.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<String, Integer> next =  iterator.next();
            if(result == "" && maxCount == 0){
                maxCount = next.getValue();
                result = next.getKey();
            }else if(next.getValue() >= maxCount){
                maxCount = next.getValue();
                result = next.getKey();
            }
        }
        return result;
    }
    public String getMinKey() {
        if(list.isEmpty()){
            return "";
        }
        int minCount = 0;
        String result = "";
        Iterator<Map.Entry<String, Integer>> iterator = list.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<String, Integer> next =  iterator.next();
            if(result == "" && minCount == 0){
                minCount = next.getValue();
                result = next.getKey();
            }
            if(next.getValue() <= minCount){
                minCount = next.getValue();
                result = next.getKey();
            }
        }
        return result;
    }
}
